package 力扣.回溯;

import javax.swing.*;
import java.util.ArrayList;
import java.util.List;

public class 组合77 {
    public List<List<Integer>> combine(int n, int k) {
        if (n == 0 || k == 0){
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        backTrace(n,1,k,ans,box);
        return ans;
    }

    private void backTrace(int n, int i, int k, List<List<Integer>> ans, List<Integer> box) {
        final int N = n;
        if (box.size() == k){
            ans.add(new ArrayList<>(box));
        }
        if (i > n || box.size() == k){
            return;
        }
        //怎么选宝石
        for (int j = i; j <= n; j++) {
            int t = j;
            box.add(t);
            backTrace(n, j + 1, k, ans, box);
            box.remove(box.size() - 1);
        }
    }

    public List<List<Integer>> combine2(int n, int k) {
        if (n == 0 || k == 0){
            return new ArrayList<>();
        }
        List<List<Integer>> ans = new ArrayList<>();
        List<Integer> box = new ArrayList<>();
        backTrace2(n,k,1,ans,box);
        return ans;
    }

    private void backTrace2(int n, int k, int i, List<List<Integer>> ans, List<Integer> box) {
        if (box.size() == k){
            ans.add(new ArrayList<>(box));
        }
        if (i > n || box.size() > k){
            return;
        }
        for (int j = i; j <= n; j++) {
            box.add(j);
            backTrace2(n, k, j + 1, ans, box);
            box.remove(box.size() - 1);
        }
    }
}
